package _2022.hot100._142_环形链表II;

import java.util.HashSet;
import java.util.Set;

/**
 * @author： YHSimon
 * @date： 2022-05-04 15:32
 */

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
  }
public class Solution {

    //哈希表
    public ListNode detectCycle2(ListNode head){
        Set<ListNode> visited=new HashSet<>();
        ListNode pos=head;
        while(pos!=null){
            if(visited.contains(pos)){
                return pos;
            }else{
                visited.add(pos);
            }
            pos=pos.next;
        }
        return null;
    }

    //快慢指针
    public ListNode detectCycle(ListNode head){
        if(head==null){
            return null;
        }
        ListNode fast=head,slow=head;
        while(fast!=null&&slow!=null){
            fast=fast.next;
            slow=slow.next;
            if(fast!=null){
                fast=fast.next;
            }else{
                return null;
            }
            if(fast==slow){
                ListNode ptr=head;
                while(ptr!=slow){
                    ptr=ptr.next;
                    slow=slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}
